package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;

public class LC1588 {

    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Solution {
        /**
         * @param n: An integer
         * @return: A list of root
         */
        public List<TreeNode> allPossibleFBT(int n) {
            //https://leetcode.cn/problems/all-possible-full-binary-trees/solutions/2719920/you-yi-dao-mo-ban-ti-dan-geng-ling-huo-x-j03j/
            List<TreeNode> list = new ArrayList<>();
            if(n ==1) {
                list.add(new TreeNode(0));
                return list;
            }

            /*
            我们现在已知信息：

            节点总数 n 一定是奇数。
            左树节点数 + 右树节点数 =n−1 (根节点占一个)。
            那么，如果左树的节点数为 i，右树节点数一定为 n−i−1。
            将 i 和 n−i−1 交给 process，让其返回信息，每次步长为 2，开始遍历。
            最后，遍历两个 list，将节点加入 res。

            作者：shiho
            链接：https://leetcode.cn/problems/all-possible-full-binary-trees/solutions/2719920/you-yi-dao-mo-ban-ti-dan-geng-ling-huo-x-j03j/
            来源：力扣（LeetCode）
            著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
             */
            for (int i = 1; i <n ; i+=2) {
                //先初次给左子节点分配一个节点
                List<TreeNode> left = allPossibleFBT(i);
                //对应的右子节点得到的结点就是总结点数量减去分配给左孩子的结点数减去根结点
                List<TreeNode> right = allPossibleFBT(n-i-1);
                for (TreeNode l : left) {
                    for (TreeNode r : right) {
                        //先将当前的根赋值，其次再将递归处理过的左右赋值，加入到数组当中
                        TreeNode root = new TreeNode(0);
                        root.left = l;
                        root.right = r;
                        list.add(root);
                    }
                }
            }

            //最后返回当前递归栈处理的好的list
            return list;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        obj.allPossibleFBT(7);
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有204条未读消息，请及时查看
1588 · 所有可能的满二叉树
算法
中等
通过率
70%

题目
题解7
笔记
讨论8
排名
记录
描述
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1 <= N <= 20

样例
样例 1：

输入：7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释：
img

样例 2:

输入：8
输出：[]
解释：没有满二叉树满足条件。
标签
企业
Google
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
…}
控制台
历史提交

 */
